package algorithm.leetcode.I201to400;

/**
 * 多状态dp
 */

// B-买入, S-卖出, K-保持, N-不可能
//
// 入\\出  买  卖  冷
//   买   K   S   N
//   卖   N   N   K
//   冷   B   N   K
//


public class Q309 {

    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;

        int buyIn = -prices[0], soldOut = 0, coolDown = 0;
        int maxVal = Integer.MIN_VALUE;

        for (int i = 1; i < prices.length; i++) {
            int lastBuyIn = buyIn, lastSoldOut = soldOut, lastCoolDown = coolDown;
            // 看状态转移矩阵的纵列选最大值更新
            coolDown = Math.max(lastCoolDown, lastSoldOut);
            soldOut = lastBuyIn + prices[i];
            buyIn = Math.max(lastBuyIn, lastCoolDown-prices[i]);
            maxVal = Math.max(Math.max(coolDown, Math.max(buyIn, soldOut)), maxVal);
        }
        return maxVal;
    }

}
